import java.util.ArrayList;
import java.util.PriorityQueue;

// 这个类用于合并K个有序链表
// 测试链接：https://www.nowcoder.com/practice/65cfde9e5b9b4cf2b6bafa5f3ef33fa6
public class Code01_MergeKSortedLists {

    // 定义链表节点类，不要提交这个内部类
    public static class ListNode {
        // 节点的值
        public int val;
        // 指向下一个节点的指针
        public ListNode next;
    }

    // 这个方法用于合并K个有序链表，需要提交这个方法
    public static ListNode mergeKLists(ArrayList<ListNode> arr) {
        // 创建一个小根堆，用于存储链表节点
        // 通过比较器 (a, b) -> a.val - b.val 来保证小根堆的特性，即堆顶元素最小
        PriorityQueue<ListNode> heap = new PriorityQueue<>((a, b) -> a.val - b.val);

        // 遍历输入的链表数组
        for (ListNode h : arr) {
            // 如果链表头节点不为空，则将其加入小根堆
            if (h!= null) {
                heap.add(h);
            }
        }

        // 如果小根堆为空，说明输入的链表数组中所有链表都是空链表，直接返回null
        if (heap.isEmpty()) {
            return null;
        }

        // 先从堆中弹出一个节点，作为合并后链表的头节点
        ListNode h = heap.poll();
        // 记录当前节点，初始化为合并后链表的头节点
        ListNode pre = h;
        // 如果头节点的下一个节点不为空，则将其加入小根堆
        if (pre.next!= null) {
            heap.add(pre.next);
        }

        // 当小根堆不为空时，继续合并链表
        while (!heap.isEmpty()) {
            // 从堆中弹出一个节点
            ListNode cur = heap.poll();
            // 将当前节点连接到合并后的链表上
            pre.next = cur;
            // 更新当前节点为刚连接上的节点
            pre = cur;
            // 如果当前节点的下一个节点不为空，则将其加入小根堆
            if (cur.next!= null) {
                heap.add(cur.next);
            }
        }

        // 返回合并后的链表头节点
        return h;
    }
}